package com.hardy.leecode;

/**
 * Author: Hardy
 * Date:   2020/12/15
 * Description:
 * - 剑指 Offer 49. 丑数
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 * <p>
 * 示例:
 * <p>
 * 输入: n = 10
 * 输出: 12
 * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 * 说明:  
 * <p>
 * 1 是丑数。
 * n 不超过1690。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/chou-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 **/
public class QueOffer49 {
    public static void main(String[] args) {

        System.out.println(new Solution().nthUglyNumber(10));
    }

    static class Solution {

        /**
         * 递推公式: a[n] = a[n-1] * (2/3/5)
         * 如何有序: min(a*2, b*3, c*5)
         */
        public int nthUglyNumber(int n) {
            // a*2 b*3 c*5
            int a = 1, b = 1, c = 1;
            int va = 0, vb = 0, vc = 0;
            int s = 1;
            int v = 0;

            /**
             * a*2 b*3 c*5 2 3 5 -> 4 6 10 15 -> 8 12 20 30 12 18 30 45
             * [1,1,1] -> (2 3 5)       -> [2,1,1]
             * [2,1,1] -> (4, 3, 5)     -> [2,3,1]
             * [2,3,1] -> (4, 9, 5)     -> [2,3,5]  [3,2,1] -> (6, 6, 5) -> [3,2,5]
             * [2,3,5] -> (4, 9, 25)    -> [4,3,5]  [5,3,2] -> (10, 9, 10) -> [5,3,2]
             * [4,3,5] -> (8, 9, 25)    -> [8,3,5]
             * [8,3,5] -> (4, 9, 25)    -> []
             */

            while (min(a, b, b) < n) {
                va = a * 2;
                vb = b * 3;
                vc = c * 5;

                v = min(va, vb, vc);

                if (va == v) a = va;
                if (vb == v) b = vb;
                if (vc == v) c = vc;
                s++;
            }
            return s;
        }

        private int min(int va, int vb, int vc) {
            int v = va;
            if (v > vb) v = vb;
            if (v > vc) v = vc;
            return vb;
        }
    }
}
